﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0139_Merge : IAlgorithm
    {
        // 合并区间

        // 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
        // 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

        // 提示：
        //  1 <= intervals.length <= 10^4
        //  intervals[i].length == 2
        //  0 <= starti <= endi <= 10^4

        public void Test()
        {
            // 算法参数定义
            var nums = new int[][] { new int[] { 1, 3 }, new int[] { 2, 6 } ,new int[] { 8,10} };
            // 算法执行与打印
            var res = Merge1(nums);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public int[][] Merge(int[][] intervals)
        {
            var result = new List<int[]>();
            var tempLst = intervals.ToList().OrderBy(x => x[0]).ThenBy(x => x[1]).ToList();
            var tempEle = tempLst[0];
            for (int i = 1; i < tempLst.Count; i++)
                if (tempEle[1] >= tempLst[i][0])
                    tempEle[1] = tempLst[i][1] > tempEle[1] ? tempLst[i][1] : tempEle[1];
                else
                {
                    result.Add(tempEle);
                    tempEle = tempLst[i];
                }
            result.Add(tempEle);
            return result.ToArray();
        }

        public int[][] Merge1(int[][] intervals)
        {
            var result = new List<int[]>();
            foreach (var item in intervals)
            {
                ConcatOrAdd(result, item);
            }
            return result.ToArray();
        }
        private void ConcatOrAdd(List<int[]> result, int[] temp)
        {
            var tempEle = result.FirstOrDefault(x => x[1] >= temp[0] && x[0] <= temp[1]);
            if (tempEle == null)
                result.Add(temp);
            else
            {
                result.Remove(tempEle);
                tempEle[0] = Math.Min(tempEle[0], temp[0]);
                tempEle[1] = Math.Max(tempEle[1], temp[1]);
                ConcatOrAdd(result, tempEle);
            }
        }
    }
}
